We investigate the following above-guarantee parameterization of theclassical Vertex Cover problem: Given a graph $G$ and $k\in\mathbb{N}$ asinput, does $G$ have a vertex cover of size at most $(2LP-MM)+k$? Here $MM$ isthe size of a maximum matching of $G$, $LP$ is the value of an optimum solutionto the relaxed (standard) LP for Vertex Cover on $G$, and $k$ is the parameter.Since $(2LP-MM)\geq{LP}\geq{MM}$, this is a stricter parameterization thanthose---namely, above-$MM$, and above-$LP$---which have been studied so far. We prove that Vertex Cover is fixed-parameter tractable for this stricterparameter $k$: We derive an algorithm which solves Vertex Cover in time$O^{*}(3^{k})$, pushing the envelope further on the parameterized tractabilityof Vertex Cover.
展开▼
机译：我们研究以下关于经典顶点覆盖问题的保证参数：给出图$ G $和$ k \ in \ mathbb {N} $作为输入，$ G $的顶点覆盖大小是否最大为$（2LP-MM ）+ k $？这里$ MM $是$ G $的最大匹配项的大小，$ LP $是$ G $上Vertex Cover松弛（标准）LP最优解的值，$ k $是参数。 2LP-MM）\ geq {LP} \ geq {MM} $，这是比到目前为止已研究的参数化严格的参数化，即高于$ MM $和高于$ LP $。我们证明对于这个更严格的参数$ k $，Vertex Cover是固定参数易处理的：我们推导了一种算法，可以在时间$ O ^ {*}（3 ^ {k}）$中求解Vertex Cover，进一步推动了信封的参数化易处理性顶点覆盖。
展开▼
